package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @author tzp
 * @since 2020/9/23
 */
public class LC10 implements DynamicProblem {
    public boolean isMatch(String s, String p) {
//        if (s.length() == 0) return p.length() == 0 || (p.length() == 2 && p.charAt(1) == '*');
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        //第一维表示字符串s的前i个字母. 第0位表示空串
        //第二位表示模式p的前i个字母. 第0位空串没啥意义肯定是false
        dp[0][0] = true;
//        for (int i = 1; i <= s.length(); i++) {
//            dp[i][0] = false;
//        }
        for (int j = 1; j <= p.length(); j++) {
            if (p.charAt(j - 1) != '*') {
                dp[0][j] = false;
            } else {
                dp[0][j] = j - 2 < 1 || dp[0][j - 2];
            }
        }
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= p.length(); j++) {
                if (p.charAt(j - 1) != '*') {
                    dp[i][j] = dp[i - 1][j - 1] && singleMatch(s, i, p, j);
                } else {
                    if (dp[i][j - 1] || (j - 2 > 0 && dp[i][j - 2])) {
                        //左侧1格或两格转移到这,分别对应*表示1和0
                        dp[i][j] = true;
                    } else if (dp[i - 1][j] && singleMatch(s, i, p, j - 1)) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = false;
                    }
                }
            }
        }
        return dp[s.length()][p.length()];
    }

    public static boolean singleMatch(String s, int i, String p, int j) {
        if (p.charAt(j - 1) == '.') {
            return true;
        } else {
            return s.charAt(i - 1) == p.charAt(j - 1);
        }
    }

    public static boolean lr(String s, String p) {
        Pattern pt = Pattern.compile(p);
        Matcher m = pt.matcher(s);
        boolean b = m.matches();
        return b;
    }

    public static void main(String[] args) {
        System.out.println(new LC10().isMatch("abbx", "a*x*m"));
        System.out.println(new LC10().isMatch("abbx", "ab*x"));
        System.out.println(new LC10().isMatch("ab", "a.*"));
        System.out.println(new LC10().isMatch("ab", "abc*"));
        System.out.println(new LC10().isMatch("a", "a.*"));
        System.out.println(new LC10().isMatch("", "a.*"));
        System.out.println(new LC10().isMatch("", "a*b*"));
    }
}
